# 火柴棒数字(好题, 一个非常典型的多重背包问题, 也就是一个物品可以选择固定的次数)


def max_matchstick_num():
    # 10个1(20) 10个7(30) 10个4(40) 10个5(50) 10个3(50) 10个2(50) 10个9(60)
    # 9 7
    pass


def max_matchstick_num_knapsack(W: int = 300):
    def add_state(state: tuple, d: int) -> tuple:
        """
        在状态 state 上加入数字 d 的贡献，返回新状态。
        state: (total_digits, f9, f8, ..., f0)
        对于数字 d，其对应在状态中位置为: index = 1 + (9 - d)
        """
        total = state[0] + 1
        # 将 state 转为列表以便修改
        lst = list(state)
        lst[0] = total
        pos = 10 - d
        lst[pos] += 1
        return tuple(lst)

    # 每个数字对应的火柴棒数目：索引对应数字 0...9
    match_cost = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    max_count_per_digit = 10  # 每个数字最多只能选 10 个

    # 这里把一个多重背包问题转换为了一个01背包(🤣)
    # 构造物品列表：每个物品为 (d, cost)
    items = []
    for d in range(10):
        for _ in range(max_count_per_digit):
            items.append((d, match_cost[d]))
    N = len(items)  # 总物品数，最多 100

    # dp[i][j]: 考虑前 i 个物品，花费恰好 j 时的最佳状态
    # 状态为元组：(total_digits, f9, f8, ..., f0)
    dp = [None] * (W + 1)
    # 初始状态
    init_state = (0,) + (0,) * 10  # 11个数字：总位数和各数字频次
    dp[0] = init_state

    for i in range(N):
        d, cost = items[i]
        # 倒序遍历 j 保证 0/1 背包性质
        for j in range(W, cost - 1, -1):
            if dp[j - cost] is not None:
                candidate = add_state(dp[j - cost], d)
                if dp[j] is None or candidate > dp[j]:
                    dp[j] = candidate

    best_state = None
    for j in range(W + 1):
        if dp[j] is not None:
            if best_state is None or dp[j] > best_state:
                best_state = dp[j]

    if best_state is None or best_state[0] == 0:
        return "0"

    ans = []
    for d in range(9, -1, -1):
        count = best_state[1 + (9 - d)]
        ans.append(str(d) * count)
    return "".join(ans)

def max_match_num_bounded(n):
    """使用多重背包的方法解决"""
    costs = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]  # 每个数字需要花费的火柴数量
    # 表示当前的选取状态, 用于比较大小, 等价于value
    # 例如当前选取10个9和7个8 那么state=(17,10,7,...)
    dp = [(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)] * (n + 1)
    for i in range(0, 10):  # 遍历每个数字
        weight = costs[i]
        for j in range(n, -1, -1):  # 逆序遍历每个背包的重量, 确保不会超过数量
            for k in range(1, 11):  # 遍历每个数字最多可以选择的次数
                if j >= weight * k:
                    state_o = dp[j]
                    state_n = list(dp[j - weight * k])
                    state_n[0] += k
                    idx = 10 - i
                    state_n[idx] = k
                    state_n = tuple(state_n)
                    if state_n > state_o:
                        dp[j] = tuple(state_n)
                else:
                    break
    res = ""
    for i in range(1, 11):
        res = res + (str(10 - i) * dp[n][i])
    return res


if __name__ == '__main__':
    print(max_matchstick_num_knapsack(300))
    print(max_match_num_bounded(300))
    print("9" * 10 + "7" * 10 + "5" * 10 + "4" * 10 + "3" * 10 + "2" * 10 + "1" * 10)
